package com.itcast.demo.simple;

import com.itcast.demo.entity.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定一棵二叉树，判断琪是否是自身的镜像（即：是否对称）
 *
 * @author zheng.zhang
 */
public class Test1 {
    public static void main(String[] args) {
        Test1 test = new Test1();
        boolean result = test.isSymmetric(null);
        System.out.println(result);
    }

    /**
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isSymmetric(TreeNode root) {
        // write code here
        if (root == null) {
            return true;
        }
        return func1(root.left, root.right);
    }

    /**
     * 递归实现
     *
     * @param left  左节点
     * @param right 右节点
     * @return 是否对称
     */
    public boolean func1(TreeNode left, TreeNode right) {
        // 如果左子树右子树都为空则该节点是对称的
        if (left == null && right == null) {
            return true;
        }
        // 有一个为空就是不对称的
        if (left == null || right == null) {
            return false;
        }
        return left.val == right.val && func1(left.left, right.right) && func1(left.right, right.left);
    }

    /**
     * 迭代实现
     *
     * @param root 根节点
     * @return 是否对称
     */
    public boolean func2(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode left = queue.poll();
                TreeNode right = queue.poll();
                size -= 2;
                if (left == null && right == null) {
                    continue;
                }
                if (left == null || right == null) {
                    return false;
                }
                if (left.val != right.val) {
                    return false;
                }
                queue.offer(left.left);
                queue.offer(right.right);
                queue.offer(left.right);
                queue.offer(right.left);
            }
        }
        return true;
    }
}
